package offer.offer04;

import java.util.ArrayList;
import java.util.List;

/**
 * 10000测试的用例时间太长, 放弃 解析未看, 需要系统看一下动态规划的视频
 * LinkedHashMap要想获得最后的值, 需要从头到尾遍历; 他这个有序性也就只有遍历的时候有用, 你想要索引是做不到的。
 * Map.Entry这玩意是个接口, 没法当自己的类用
 *
 * 数组中一前一后, 后减前的最大值;
 * 创建两个链
 * 第一个, 买入链, 从右向左扫描, 每遇到一个点, 把买入链该点之前的所有大于该点的值都删除,
 * 表示该点可以替代那些点; 注意, 如果前面剔除到前面没有比他大的点之后, 他自己是要放进去的,
 * 也就是说, 如果前面是6, 4, 2, 这时扫到了3, 是要变成6 4 2 3的。
 * 第二个, 卖出链, 从左向右扫描, 每遇到一个点, 把卖出链该点之前的所有小于该点的值都删除
 * 表示该点比那些被删除的点强(选择该点的收益更高, 同时如果前面的点符合条件, 该点也符合条件);
 *
 */
public class S63股票的最大利润fail {
    class myEntry{
        private int key;
        private int value;

        public myEntry(int key, int value) {
            this.key = key;
            this.value = value;
        }
        public int getKey(){
            return this.key;
        }
        public int getValue() {
            return this.value;
        }

        @Override
        public String toString() {
            return "myEntry{" +
                    "key=" + key +
                    ", value=" + value +
                    '}';
        }
    }
    public int maxProfit(int[] prices) {
        List<myEntry> buyList = new ArrayList<>();
        List<myEntry> sellList = new ArrayList<>();
        for(int i = prices.length - 1; i >= 0; i--){
            while (buyList.size() != 0 && buyList.get(buyList.size() - 1).getValue() > prices[i]){
                buyList.remove(buyList.size() - 1);
            }
            buyList.add(new myEntry(i, prices[i]));
        }
        for(int i = 0; i < prices.length; i++){
            while (sellList.size() != 0 && sellList.get(sellList.size() - 1).getValue() < prices[i]){
                sellList.remove(sellList.size() - 1);
            }
            sellList.add(new myEntry(i, prices[i]));
        }
        System.out.println("buyList: " + buyList);
        System.out.println("sellList: " + sellList);

        int maxGain = 0;
        int curPosi = 0;//我们记一下sell开始的时间
        for(int i = buyList.size() - 1; i >= 0; i--){
            //按照在prices中从左到右的顺序遍历buy
            for(int j = 0; j < sellList.size(); j++){
                if(sellList.get(j).getKey() > buyList.get(i).getKey()){
                    maxGain = Math.max(sellList.get(j).getValue() - buyList.get(i).getValue(), maxGain);
                }
            }
        }
        return maxGain;
    }

}
